'''
Created on Aug 20, 2009

@author: echeek
'''


memoization=dict();
memcount=0;

squares=[];
for v in (x**2 for x in range(10)):
    squares.append(v);

def permutationGroup(value):
    import math
    counts=[0]*10;
    while(value>0):
        counts[value%10]+=1;
        value=int(math.floor(value/10));
    return tuple(counts); 

def nextTerm(v):
    sum=0;
    while v>0:
        sum+=squares[v%10];
        v=int(v/10);
    return sum;

def trackChain(value):
    global memcount
    visited=[];
    term=value;
    while term!=1 and term!=89:
        #memval=permutationGroup(term);
        memval=term;
        visited.append(memval);
        
        if(memval in memoization):
            term=89 if memoization[memval] else 1;
            memcount+=1;
            break;
        term=nextTerm(term);
    if value<600:
        for i in visited:
            memoization[i]=(term==89);
    return term==89;
    
    

def Euler92():
    count=0;
    for i in range(1,10000000):
        if(trackChain(i)):
            count+=1;
        if(i%100==0):
            print str(memcount)+"/"+str(i);
    print count;
    
Euler92();

    